import java.util.LinkedList;

/**
 * 简易拉链法实现哈希表
 */
public class ExampleChainingHashMap {

    // 链表节点，存储key-value键值对
    // 注意：必须同时存储key值和value值，确保可通过key值获取value值
    private static class KVNode {
        int key, value;
        KVNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 底层table数组中的每个元素都是一个链表
    private LinkedList<KVNode> table[];

    public ExampleChainingHashMap(int capacity) {
        table = new LinkedList[capacity];
    }

    private int hash(int key) {
        return key % table.length;
    }

    public int get(int key) {
        int index = hash(key);
        if (table[index] ==  null) {
            // 链表为空，说明key不存在
            return -1;
        }
        LinkedList<KVNode> list = table[index];
        // 遍历链表，尝试查找key对应的value
        for (KVNode node: list) {
            if (node.key == key) {
                return node.value;
            }
        }

        // 链表中没有对应的value，说明key不存在
        return -1;
    }

    public void put(int key, int value) {
        int index = hash(key);
        if (table[index] == null) {
            // 链表为空，创建一个链表，插入key-value键值对
            table[index] = new LinkedList<>();
            table[index].add(new KVNode(key, value));
            return;
        }

        // 链表不为空，要遍历一遍看看key是否已然存在
        // 如果存在，则更新value值
        // 不存在，插入新节点
        LinkedList<KVNode> list = table[index];
        for (KVNode kvNode : list) {
            if (kvNode.key == key) {
                kvNode.value = value;
                return;
            }
        }
        // 链表中不存在对应的key，插入新节点
        list.addLast(new KVNode(key, value));
    }

    public void remove(int key) {
        LinkedList<KVNode> list = table[hash(key)];
        if (list == null)
            return;

        // 如若key存在，则删除
        list.removeIf(node -> node.key == key);
    }
    public static void main(String[] args) {

    }
}
